//请设计一个函数判断一棵二叉树是否 轴对称 。
//
//
//
// 示例 1：
//
//
//
//
//输入：root = [6,7,7,8,9,9,8]
//输出：true
//解释：从图中可看出树是轴对称的。
//
// 示例 2：
//
//
//
//
//输入：root = [1,2,2,null,3,null,3]
//输出：false
//解释：从图中可看出最后一层的节点不对称。
//
//
//
// 提示：
//
// 0 <= 节点个数 <= 1000
//
// 注意：本题与主站 101 题相同：https://leetcode-cn.com/problems/symmetric-tree/
//
//
//
// Related Topics 树 深度优先搜索 广度优先搜索 二叉树 👍 483 👎 0


package LeetCode.editor.cn;

import java.util.LinkedList;

/**
 * @author ldltd
 * @date 2025-05-01 14:32:09
 * @description LCR 145.判断对称二叉树
 */
public class DuiChengDeErChaShuLcof{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 DuiChengDeErChaShuLcof fun=new DuiChengDeErChaShuLcof();
	 	 Solution solution = fun.new Solution();

	 }

//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)

 // Definition for a binary tree node.
 public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
     TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

class Solution {
         //dfs或者bfs
    public boolean checkSymmetricTree1(TreeNode root) {
        if(root==null) return true;
        return isSyn(root.left,root.right);
    }
    private boolean isSyn(TreeNode l,TreeNode r){
        if(l==null||r==null) return r==null&&l==null;
        else if(l.val==r.val&&(isSyn(l.left,r.right)&&isSyn(l.right,r.left))) return true;
        return false;
    }

    public boolean checkSymmetricTree(TreeNode root) {
        if(root==null || (root.left==null && root.right==null)) {
            return true;
        }
        //用队列保存节点
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        //将根节点的左右孩子放到队列中
        queue.add(root.left);
        queue.add(root.right);
        while(queue.size()>0) {
            //从队列中取出两个节点，再比较这两个节点
            TreeNode left = queue.removeFirst();
            TreeNode right = queue.removeFirst();
            //如果两个节点都为空就继续循环，两者有一个为空就返回false
            if(left==null && right==null) {
                continue;
            }
            if(left==null || right==null) {
                return false;
            }
            if(left.val!=right.val) {
                return false;
            }
            //将左节点的左孩子， 右节点的右孩子放入队列
            queue.add(left.left);
            queue.add(right.right);
            //将左节点的右孩子，右节点的左孩子放入队列
            queue.add(left.right);
            queue.add(right.left);
        }

        return true;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
